package tul.cot;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import tul.cot.exception.ParseTreeException;


public class MigrationTree {
	
	public static final String NAME_LENGTH_SEP = ":";
	private static final String UNEXPECTED_CHAR_FORMAT = "Unexpected char '%c' at pos %d";
	private static final String EXPECTED_CHAR_FORMAT = "Expected '%c' at pos %d, but was '%c'";
	
	private String label;
	private MigrationTree parent;
	private double length = -1;
//	private double new_depth = 0;
	private double time = Double.MIN_VALUE;
	private double maxToLeaf = Double.MIN_VALUE;
	private double minToLeaf = Double.MAX_VALUE;
	List<MigrationTree> sons = new ArrayList<MigrationTree>();
	
	public MigrationTree(String treeStr) throws ParseTreeException {
		parse(treeStr);
		
	}

	MigrationTree(String label, MigrationTree parent, double length) {
		this.label = label;
		this.parent = parent;
		this.length = length;
//		this.new_depth = parent.new_depth + this.length;
	}
	
	public String getLabel() {
		return label;
	}
	
	public double getLength() {
		return length;
	}
	
	public MigrationTree getParent() {
		return parent;
	}
	
	public Iterable<MigrationTree> getSons() {
		return sons;
	}
	
	public int getNumSons() {
		return sons.size();
	}
	
	public boolean isLeaf() {
		return getNumSons() == 0;
	}
	
	public boolean isRoot() {
		return getParent() == null;
	}
	
	public double getTime() {
		return this.time;
	}
	
	public boolean isUltrametric(double eps) {
		return (maxToLeaf - minToLeaf) < eps;
	}
	
	/**
	 * Moves all leaves to the same level by increasing length of their edges.
	 * The method sets times, too (all leaves have time = 0).
	 */
	public void makeUltrametric() {
		double expLeafTime = -10E9; // -eps < 0
		Deque<MigrationTree> q = new ArrayDeque<MigrationTree>(1000);
		this.time = this.maxToLeaf;
		q.addFirst(this);
		
		while (!q.isEmpty()) {
			MigrationTree tree = q.removeFirst();
			
			if (!tree.isRoot()) {
				tree.setNodeTime();
			}
			
			if (tree.isLeaf()) {
				tree.moveToExpTime(expLeafTime);
			} else {
				for (MigrationTree son: tree.getSons()) {
					q.addLast(son);
				}
			}
		}
	}
	
	private void setNodeTime() {
		this.time = this.getParent().getTime() - this.getLength();
	}

	private void moveToExpTime(double expTime) {
		double lengthToAdd = this.getTime() - expTime;
		this.length += lengthToAdd;
		
		if (this.length < 0)
			throw new IllegalArgumentException("Wrong expTime value (length < 0)");
		
		this.setNodeTime();
	}
	
	/**
	 * Sets times to nodes that the deepest node has the time = 0
	 */
	public void setTimes() {
		setTime(maxToLeaf);
	}
	
	private void setTime(double startTime) {
		Deque<MigrationTree> q = new ArrayDeque<MigrationTree>(1000);
		this.time = startTime;
		q.addFirst(this);
		
		while (!q.isEmpty()) {
			MigrationTree tree = q.removeFirst();
			
			if (!tree.isRoot()) {
				tree.time = tree.getParent().getTime() - tree.getLength();
			}
			
			for (MigrationTree son: tree.getSons()) {
				q.addLast(son);
			}
		}		
	}
	
	private void parse(String treeStr) throws ParseTreeException {
		
		char[] t = treeStr.toCharArray();
		int pos = t.length - 1;
		if (t[pos] == ';')
			--pos;
		int next = findSpecialChar(pos, t);
		
		
		
		//root
		this.label = treeStr.substring(next+1, pos+1);
		this.parent = null;
		this.length = 0;
//		this.new_depth = 0;
		
		if (next < 0)
			return;
		
		if (t[next] != ')' || next == 0)
			throw new ParseTreeException(String.format(UNEXPECTED_CHAR_FORMAT, t[next], next));
		
		MigrationTree root = this;
		pos = next - 1;
		
		// niezmiennik == (root, pos)
		while (pos >= 0) {
			next = findSpecialChar(pos, t);
			
			if (next < 0)
				throw new ParseTreeException(String.format("next < 0, pos = %d", pos));
			
			MigrationTree tree = createNewTree(t, next+1, pos, root);
			root.sons.add(tree);
			
			switch (t[next]) {
				case ')':
					root = tree;
					pos = next - 1;
					continue;
//				break;
				
				case ',':
					pos = next - 1;
					continue;
//				break;
				
				case '(':
					while (next >= 0 && t[next] == '(') {
						if (root == null)
							throw new ParseTreeException(String.format(UNEXPECTED_CHAR_FORMAT, t[next], next));
						
						root.computeDepths();
						root = root.parent;
						--next;
					}
					
					if (next < 0) {
						if (root != null)
							throw new ParseTreeException("Unfinished parsing");
						
						pos = next;
						continue;
					} else { // next >= 0
						if (t[next] != ',')
							throw new ParseTreeException(String.format(EXPECTED_CHAR_FORMAT, ',', next, t[next]));
						
						pos = next - 1;
						continue;
					}
//				break;

			default:
				throw new ParseTreeException(String.format(UNEXPECTED_CHAR_FORMAT, t[next], next));
			}
		}
		
		if (root != null)
			throw new ParseTreeException("Unfinished parsing");
	}

	private void computeDepths() {
		this.maxToLeaf = isLeaf() ? 0 : Double.MIN_VALUE;
		this.minToLeaf = isLeaf() ? 0 : Double.MAX_VALUE;
		
		for (MigrationTree son: sons) {
			this.maxToLeaf = Math.max(this.maxToLeaf, son.maxToLeaf + son.length);
			this.minToLeaf = Math.min(this.minToLeaf, son.minToLeaf + son.length);
		}
	}

	private int findSpecialChar(int start, char[] t) {
		for (int i=start; i>=0; --i) {
			if (specialChar(t[i]))
				return i;
		}
		
		return -1;
	}

	private boolean specialChar(char c) {
		return c == '(' || c == ')' || c == ',';
	}
	
	/**
	 * @param t tree char array
	 * @param first first char index of "<name>:<length>" e.g. "Europe:0.5"
	 * @param last last char index of "<name>:<length>" e.g. "Europe:0.5"
	 * @param parent parent node
	 * @return
	 */
	private MigrationTree createNewTree(char[] t, int first, int last, MigrationTree parent) {
		String rootStr = new String(t, first, last - first + 1);
		
		String[] split = rootStr.split(NAME_LENGTH_SEP);
		String label = split[0];
		String lengthStr = split[1];
		double length = Double.parseDouble(lengthStr);
		
		return new MigrationTree(label, parent, length);
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		if (sons.size() > 0) {
			sb.append('(');
			sb.append(sons.get(0).toString());
			for (int i=1; i<sons.size(); ++i) {
				sb.append(',');
				sb.append(sons.get(i).toString());
			}
			sb.append(')');
		}
		
		sb.append(label);
		if (!isRoot()) {
			sb.append(':');
			sb.append(length);
		}
		
		sb.append("[" + time + "]");
		
		return sb.toString();
	}
	
}
